#include <iostream>
#include <map>
#include <set>
#include <climits>
#include <vector>
#include <stdio.h>
#include <string.h>

#include <list>
#include <stdlib.h>
#include <sys/time.h>  

timeval tm1, tm2;

using namespace std;
int limitePeligro = 10;
int cantidadCargas;
list<int> cargasDisponibles;
map< int, set<int> > camionesUtilizados;
pair<int, map< int, set<int> > > resultado;
vector< vector<int> > matris;

typedef struct {
    int camiones;
    map< int, set<int> > cargas;
    vector<int> sumas;

} solucion;


int profundidad = 0;



void printProfundidad() {
    for (int j = 0; j < profundidad; j++) printf("\t");
}

void printCamion(set<int > d) {
    //printf(" c:");
    for (set<int>::iterator it = d.begin(); it != d.end(); ++it) {
        //printf("%d,", *it);
    }
    //printf(" - ");
}

void printResult(solucion result) {
    //printProfundidad();
    // printf("Resultado \n");
    // printProfundidad();
    //printf("necesito %d camiones ", result.camiones);
    printf("%d", result.camiones);
    for (int i = 0; i < cantidadCargas; i++) {
        for (map< int, set<int> > ::iterator it = (result.cargas).begin();
                it != (result.cargas).end();
                it++) {
            if ((it->second).find(i) != (it->second).end()) {
                //printf(" %d", i);
                printf(" %d", it->first + 1);
                // printProfundidad();
                // printf("camino %d",it->first);			
                // printCamion(it->second);
                // printf(" - suma - %d",sumarCamion(it->second,it->first));
            }
        }
    }
    printf("\n");
}

void printDisponibles(list<int > d) {
    printf(" d:");
    for (list<int>::iterator it = d.begin(); it != d.end(); ++it) {
        printf("%d,", *it);
    }
    printf(" - \n");

}

int sumarCamion(int carga, set<int> camion, int camionId, int sumaPrevia) {
    int total = sumaPrevia;
    for (set<int>::iterator inIt = camion.begin(); inIt != camion.end(); ++inIt) {
        if (carga < *inIt) {
            total += matris[carga][*inIt - carga - 1];
        }
        if (carga > *inIt) {
            total += matris[*inIt][carga - *inIt - 1];
        }

    }
    return total;
}


solucion ubicarCargas(
        list<int> cargasDisponibles,
        int limiteCamiones,
        int limitePeligro,
        solucion camiones) {

    list<int > disponibles;
    profundidad += 1;
    solucion  result, mejorResult;    
    mejorResult.camiones  = 0;

    if (cargasDisponibles.size() == 0) {
        profundidad -= 1;
            return camiones;
    }
    for (list<int>::iterator it = cargasDisponibles.begin();
     it != cargasDisponibles.end(); ++it) {
        //extraigo la carga *it;
        //para las cargas restantes copio y llamo recursivamente
        disponibles = cargasDisponibles;
        disponibles.remove(*it);
            for (map< int, set<int> >::iterator cit = camiones.cargas.begin(); 
            	cit != camiones.cargas.end(); cit++) {
                result = camiones;

                int s = sumarCamion(*it, result.cargas[cit->first], 
                	cit->first, result.sumas[cit->first]);
                if (s <= limitePeligro) {
                    //printf("lo voy a poder agregar suma %d %d\n", s, limitePeligro);
                    (result.cargas[cit->first]).insert(*it);
                    if (result.sumas.size() < cit->first + 1) {
                        result.sumas.resize(result.sumas.size() + 1);
                    }
                    result.sumas[cit->first] = s;
                    result = ubicarCargas(
                            disponibles,
                            limiteCamiones,
                            limitePeligro,
                            result);
                    if (result.camiones> 0 && 
                    	(result.camiones < mejorResult.camiones || 
                    		mejorResult.camiones == 0)) {
                        
                        mejorResult = result;
                        limiteCamiones = mejorResult.camiones;

                    }
                }
            }
//como ultima opcion aparte de probar ubicar la carga en los 
//camiones ya disponibles esta la posibilidad de agregar un camion para esta carga
//siempre y cuando esto no me haga excederme de la mejor disposicion que pude generar
            if ( limiteCamiones-1 > camiones.camiones) {
                //printf("inserte un camion mas\n");
                result = camiones;
                result.camiones += 1;
                int cantC = (result.cargas).size();
                (result.cargas).insert(std::pair< int, set<int> > (cantC,{}));
                (result.cargas[cantC]).insert(*it);
                result.sumas.resize(result.camiones);
	            result.sumas[cantC] = 0;               
                result = ubicarCargas(
                        disponibles,
                        limiteCamiones,
                        limitePeligro,
                        result);

                if (result.camiones> 0 && 
                	(result.camiones < mejorResult.camiones 
                		|| mejorResult.camiones == 0)) {
                  
                    mejorResult = result;
                    limiteCamiones = mejorResult.camiones;
                }

            } 

        //}
    }
    //printf("salio a ubicar cargas %d  first %d\n", profundidad, mejorResult.camiones);
    profundidad -= 1;

    return mejorResult;
}

int main(int argc, char** argv) {
    /*
    int limitePeligro = 10;
    int cantidad 
    set<int> cargasDisponibles;
    map< int,set<int> > camionesUtilizados;
    pair<int, map< int,set<int> > > resultado;
    vector< vector<int> > matris;
     */

    solucion camiones;
    camiones.camiones = 0;
    char line[1000];
    vector<int> reader;
    reader.resize(5);
    char* strVal;
    int val;
    int readedLine = 0;
    vector <int> instanceTitle(5);
    vector< vector<int> > values;
    solucion result;



    clock_t t;

    while (cin.getline(line, 999, '\n')) {
        if (readedLine == 1) {
            readedLine -= 1;
            // printf("termino la carga \n");				
            gettimeofday(&tm1, NULL);
            //t = clock();
            result = ubicarCargas(cargasDisponibles, INT_MAX, limitePeligro, camiones);
            //t = clock() - t;			
            gettimeofday(&tm2, NULL);
            unsigned long long int t = (tm2.tv_sec - tm1.tv_sec);
            //printf("cargas %d, camiones %d, ticks %lld\n", cargasDisponibles.size(), result.camiones, t);
            // printf("%d,%ld,%ld,%ld,%ld\n", cargasDisponibles.size(), 
            // 	tm2.tv_sec,
            // 	tm2.tv_usec, 
            // 	tm1.tv_sec,
            // 	tm1.tv_usec);
            //printf ("%d,%0.6f\n",cargasDisponibles.size(),((float)t)/CLOCKS_PER_SEC);
            printResult(result);
            continue;

        }
        if (readedLine == 0) {
            strVal = strtok(line, " ");
            cantidadCargas = atoi(strVal);

            strVal = strtok(NULL, " ");
            limitePeligro = atoi(strVal);
            readedLine = cantidadCargas;

            matris.resize(readedLine - 1);

            cargasDisponibles.clear();
            for (int i = 0; i < cantidadCargas; i++) {
                cargasDisponibles.push_back(i);
            }

        } else {
            (matris[cantidadCargas - readedLine]).resize(0);
            strVal = strtok(line, " ");
            for (int i = 0; i < readedLine - 1; i++) {
                val = atoi(strVal);
                (matris[cantidadCargas - readedLine]).push_back(atoi(strVal));
                strVal = strtok(NULL, " ");
            }
            readedLine -= 1;

        }
    }
    return 0;
}
